package lcr;

import java.util.Arrays;
import java.util.HashMap;

public class Test0075 {
}

class Solution0075 {
    HashMap<Integer, Integer> map;
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        map = new HashMap<>();
        for (int i = 0; i < arr2.length; i++) map.put(arr2[i], i);
        Arrays.sort(arr1);

        quickSort(arr1,0,arr1.length-1);
        return arr1;
    }

    public void quickSort(int[] arr, int left, int right) {
        if (left < right){
            int mid = quick(arr, left, right);

            if (mid>0) quickSort(arr, left, mid-1);
            if (mid<arr.length-2) quickSort(arr, mid+1, right);
        }
    }

    public int quick(int[] arr, int left, int right){
        int pivot = arr[right];
        int point = left;

        for (int i=left;i<right;i++){
            int cur = arr[i];
            if (compare(cur,pivot)>0){
                swap(i,point,arr);
                point++;
            }
        }

        swap(point,right,arr);
        return point;
    }

    public int compare(int a, int b) {
        if (map.containsKey(a) && map.containsKey(b)) {
            return map.get(a) - map.get(b);
        } else if (map.containsKey(a)) {
            return -1;
        } else if (map.containsKey(b)) {
            return 1;
        } else {
            return a - b;
        }
    }

    public void swap(int a,int b,int[] arr){
        int temp = arr[a];
        arr[a]=arr[b];
        arr[b]=temp;

    }
}